package com.zhugang.week10;

/**
 * @program algorithms
 * @description: bagesByDP
 * @author: chanzhugang
 * @create: 2022/08/28 20:48
 */
public class BagesByDP {

    /**
     * 0-1背包问题
     * 动态规划解法 ：本行推导出下一行
     *
     * @param weight
     * @param n
     * @param w
     * @return
     */
    public int knapsack(int[] weight, int n, int w) {
        // 定义状态
        boolean[][] dp = new boolean[n][w + 1];
        // 初始化第一行
        dp[0][0] = true;
        if (weight[0] <= w) {
            dp[0][weight[0]] = true;
        }

        // 第一种方式
      /*  for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                if (dp[i - 1][j] == true) {
                    // i- 1 推导 i
                    dp[i][j] = true;
                    if (j + weight[i] <= w) {
                        dp[i][j + weight[i]] = true;
                    }
                }
            }
        }*/

        // 第二种方式：推荐这种动态转移方程
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                if (dp[i - 1][j] || (j - weight[i] >= 0 && dp[i - 1][j - weight[i]])) {
                    dp[i][j] = true;
                }
            }
        }
        // 输出结果：从后扫描
        for (int i = w; i >= 0; i--) {
            if (dp[n - 1][i]) {
                return i;
            }
        }
        return 0;
    }
}